# 内存消耗很少，时间击败 50%，内存击败 90%
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.smap = {}

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        self.smap[word] = True
        wlen = len(word)

        for i in range(1, wlen):
            substr = word[:i]
            if substr not in self.smap:
                self.smap[substr] = False

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        if word in self.smap:
            return self.smap[word]
        else:
            return False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        return prefix in self.smap


# Your Trie object will be instantiated and called as such:
trie = Trie()

trie.insert("ab");
print(trie.search("a"))   # 返回 false
print(trie.startsWith("a")) # 返回 true
